package demo.hashmap;


import java.util.ArrayList;
import java.util.Date;
import java.util.HashMap;
import java.util.List;

/**
 * @author : feixiang.li
 * @since : 2025-09-18 16:53
 */
public class MyHashMap<K, V> {
    private static final int DEFAULT_INITIAL_CAPACITY = 16;

    public Node<K, V>[] table = new Node[DEFAULT_INITIAL_CAPACITY];

    int size;

    int threshold = (int) (DEFAULT_INITIAL_CAPACITY * 0.75f);

    public int size() {
        return size;
    }

    public class Node<K, V> {
        K key;
        V value;
        // 计算完的hash值
        int hash;
        Node<K, V> next;

        public Node(K key, V value, Node<K, V> next, int hash) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    static final int hash(Object key) {
        int h;
        /*
         * h >>> 16：将h无符号右移16位（高位补0）
         * ^：按位异或操作
         * 目的是将高16位的信息混合到低16位中
         */
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

    static final int indexFor(int hash, int length) {
        /*
         * HashMap使用(n - 1) & hash计算数组索引（n是数组长度）
         * 当数组长度较小时（如16），只有低4位参与运算，高位的变异性被浪费
         * 解决方案：通过异或操作，让高位参与影响低位，增加哈希值的随机性
         */
        return hash & (length - 1);
    }

    public V put(K key, V value) {
        // 触发一下扩容
        resize();
        int hash = hash(key);
        int index = indexFor(hash, table.length);
        Node<K, V> node = table[index];
        if (node == null) {
            size++;
            table[index] = new Node<>(key, value, null, hash);
            return null;
        }
        while (true) {
            // 判断key是否相等。如果是则更新value并返回。
            if (node.key.equals(key)) {
                V oldValue = node.value;
                node.value = value;
                return oldValue;
            }
            Node pre = node;
            node = node.next;
            if (node == null) {
                size++;
                Node<K, V> newNode = new Node<>(key, value, null, hash);
                pre.next = newNode;
                return null;
            }
        }
    }

    public V get(K key) {
        int hash = hash(key);
        int index = indexFor(hash, table.length);
        Node<K, V> node = table[index];
        while (node != null) {
            if (node.key.equals(key)) {
                return node.value;
            }
            node = node.next;
        }
        return null;
    }

    public void resize() {
        // 当 数组长度达到阈值时，进行扩容
        if (size >= threshold) {
            Node<K, V>[] oldTable = table;
            int oldCapacity = table.length;
            int newCapacity = oldCapacity * 2;
            threshold = (int) (newCapacity * 0.75f);
            Node<K, V>[] newTable = (Node<K, V>[]) new Node[newCapacity];
            table = newTable;
            for (int i = 0; i < oldCapacity; i++) {
                Node<K, V> node = oldTable[i];
                // 就这一步。差异50倍性能差距。分别加上或者注释掉
                oldTable[i] = null;
                // 遍历链表。如果不为空，则遍历链表
                if (node != null) {

                    // 表示只有一个节点
                    if (node.next == null) {
                        newTable[node.hash & (newCapacity - 1)] = node;
                        continue;
                    }

                    // 表示有多个节点。
                    // 假设：
                    //oldCap = 16 (二进制: 10000)
                    //newCap = 32 (二进制: 100000)
                    //hash值某位：如果hash值的第5位(从0开始)为0，则新位置=原位置；如果为1，则新位置=原位置+16
                    //text
                    //原索引计算：hash & 15 (01111)
                    //新索引计算：hash & 31 (11111)
                    // 原先的连表分为了2个部分。第一个还是原来的位置。第二个是原位置index+队列数量
                    /*
                       if ((e.hash & oldCap) == 0) {
                            // 新位置 = 原位置 j
                            newTab[j] = loHead;
                        } else {
                            // 新位置 = 原位置 j + oldCap
                            newTab[j + oldCap] = hiHead;
                        }
                     */

                    // 原先的连表分为了2个部分。第一个还是原来的位置。第二个是原位置index+队列数量
                    Node<K, V> lowHead = null, highHead = null;
                    Node<K, V> lowTail = null, highTail = null;
                    Node<K, V> next = null;
                    do {
                        // 表示当前节点的下一个节点 。如果第一次进来。就是原来的头节点
                        next = node.next;
                        // 表示当前节点 还是处于原来位置的 链表 low 链表
                        if ((node.hash & oldCapacity) == 0) {
                            if (lowTail == null) {
                                lowHead = node;
                            } else {
                                lowTail.next = node;
                            }
                            // low 链表 尾节点=当前节点。因为是尾插法
                            lowTail = node;
                        } else {
                            // 处于高位置的 链表 high 链表
                            // 如果high 链表 尾节点为空。则high 链表头节点=当前节点。
                            if (highTail == null) {
                                highHead = node;
                            } else {
                                // high 链表 尾节点=当前节点。因为是尾插法
                                highTail.next = node;
                            }
                            // high 链表 尾节点=当前节点。因为是尾插法
                            highTail = node;
                        }
                        node = next;
                    } while (node != null);

                    //  low 链表头节点不为空。则low 链表头节点=lowHead
                    if (lowHead != null) {
                        lowTail.next = null;
                        newTable[i] = lowHead;
                    }
                    //  high 链表头节点不为空。则high 链表头节点=highHead
                    if (highHead != null) {
                        highTail.next = null;
                        newTable[i + oldCapacity] = highHead;
                    }
                }
            }

            System.out.println("触发了扩容" + threshold + "table-长度" + table.length);
        }

    }

    public V remove(K key) {
        int hash = hash(key);
        int index = indexFor(hash, table.length);
        Node<K, V> node = table[index];
        if (node == null) {
            return null;
        }
        // 判断移除的节点是否是头节点
        if (node.key.equals(key)) {
            table[index] = node.next;
            size--;
            return node.value;
        }
        // 如果不是头节点
        Node<K, V> pre = node;
        node = node.next;
        while (node != null) {
            if (node.key.equals(key)) {
                pre.next = node.next;
                size--;
                return node.value;
            }
            pre = node;
            node = node.next;
        }

        return null;
    }
}
